Power in unity forming teams in large%2Dscale community systems.

Online Network Design with Outliers.

An optimization framework for query recommendation.
Query recommendation is an integral part of modern search engines. The goal of query recommendation is to facilitate users while searching for information. Query recommendation also allows users to explore concepts related to their information needs. In this paper, we present a formal treatment of the problem of query recommendation. In our framework we model the querying behavior of users by a probabilistic reformulation graph, or query-flow graph [Boldi et al. CIKM 2008]. A sequence of queries submitted by a user can be seen as a path on this graph. Assigning score values to queries allows us to define suitable utility functions and to consider the expected utility achieved by a reformulation path on the query-flow graph. Providing recommendations can be seen as adding shortcuts in the query-flow graph that“nudge”the reformulation paths of users, in such a way that users are more likely to follow paths with larger expected utility. We discuss in detail the most important questions that arise in the proposed framework. In particular, we provide examples of meaningful utility functions to optimize, we discuss how to estimate the effect of recommendations on the reformulation probabilities, we address the complexity of the optimization problems that we consider, we suggest efficient algorithmic solutions, and we validate our models and algorithms with extensive experimentation. Our techniques can be applied to other scenarios where user behavior can be modeled as a Markov process.
Sort Me If You Can How to Sort Dynamic Data.
Abstract. We formulate and study a new computational model for dynamic data. In this model the data changes gradually and the goal of an algorithm is to compute the solution to some problem on the data at each time step, under the constraint that it only has a limited access to the data each time. As the data is constantly changing and the algorithm might be unaware of these changes, it cannot be expected to always output the exact right solution; we are interested in algorithms that guarantee to output an approximate solution. In particular, we focus on the fundamental problems of sorting and selection, where the true ordering of the elements changes slowly. We provide algorithms with performance close to the optimal in expectation and with high probability. 1
Online pairing of VoIP conversations.

Influence and correlation in social networks.
In many online social systems, social ties between users play an important role in dictating their behavior. One of the ways this can happen is through social influence, the phenomenon that the actions of a user can induce his/her friends to behave in a similar way. In systems where social influence exists, ideas, modes of behavior, or new technologies can diffuse through the network like an epidemic. Therefore, identifying and understanding social influence is of tremendous interest from both analysis and design points of view. This is a difficult task in general, since there are factors such as homophily or unobserved confounding variables that can induce statistical correlation between the actions of friends in a social network. Distinguishing influence from these is essentially the problem of distinguishing correlation from causality, a notoriously hard statistical problem. In this paper we study this problem systematically. We define fairly general models that replicate the aforementioned sources of social correlation. We then propose two simple tests that can identify influence as a source of social correlation when the time series of user actions is available. We give a theoretical justification of one of the tests by proving that with high probability it succeeds in ruling out influence in a rather general model of social correlation. We also simulate our tests on a number of examples designed by randomly generating actions of nodes on a real social network (from Flickr) according to one of several models. Simulation results confirm that our test performs well on these data. Finally, we apply them to real tagging data on Flickr, exhibiting that while there is significant social correlation in tagging behavior on this system, this correlation cannot be attributed to social influence.
Approximation algorithms for co%2Dclustering.
Co-clustering is the simultaneous partitioning of the rows and columns of a matrix such that the blocks induced by the row/column partitions are good clusters. Motivated by several applications in text mining, market-basket analysis, and bioinformatics, this problem has attracted severe attention in the past few years. Unfortunately, to date, most of the algorithmic work on this problem has been heuristic in nature. In this work we obtain the first approximation algorithms for the co-clustering problem. Our algorithms are simple and obtain constant-factor approximation solutions to the optimum. We also show that co-clustering is NP-hard, thereby complementing our algorithmic result.
Effective and efficient classification on a search%2Dengine model.
Traditional document classification frameworks, which apply the learned classifier to each document in a corpus one by one, are infeasible for extremely large document corpora, like the Web or large corporate intranets. We consider the classification problem on a corpus that has been processed primarily for the purpose of searching, and thus our access to documents is solely through the inverted index of a large scale search engine. Our main goal is to build the “best” short query that characterizes a document class using operators normally available within large engines. We show that surprisingly good classification accuracy can be achieved on average over multiple classes by queries with as few as 10 terms. Moreover, we show that optimizing the efficiency of query execution by careful selection of these terms can further reduce the query costs. More precisely, we show that on our set-up the best 10 terms query can achieve 90 % of the accuracy of the best SVM classifier (14000 terms), and if we are willing to tolerate a reduction to 86 % of the best SVM, we can build a 10 terms query that can be executed more than twice as fast as the best 10 terms query.
Just%2Din%2Dtime contextual advertising.
Contextual Advertising is a type of Web advertising, which, given the URL of a Web page, aims to embed into the page (typically via JavaScript) the most relevant textual ads available. For static pages that are displayed repeatedly, the matching of ads can be based on prior analysis of their entire content; however, ads need to be matched also to new or dynamically created pages that cannot be processed ahead of time. Analyzing the entire body of such pages onthe-fly entails prohibitive communication and latency costs. To solve the three-horned dilemma of either low-relevance or high-latency or high-load, we propose to use text summarization techniques paired with external knowledge (exogenous to the page) to craft short page summaries in real time. Empirical evaluation proves that matching ads on the basis of such summaries does not sacrifice relevance, and is competitive with matching based on the entire page content. Specifically, we found that analyzing a carefully selected 5% fraction of the page text sacrifices only 1%–3 % in ad relevance. Furthermore, our summaries are fully compatible with the standard JavaScript mechanisms used for ad placement: they can be produced at ad-display time by simple additions to the usual script, and they only add 500–600 bytes to the usual request.
Finding %22Who Is Talking to Whom%22 in VoIP Networks via Progressive Stream Clustering.

Effective and efficient classification on a search%2Dengine model.
Traditional document classification frameworks, which apply the learned classifier to each document in a corpus one by one, are infeasible for extremely large document corpora, like the Web or large corporate intranets. We consider the classification problem on a corpus that has been processed primarily for the purpose of searching, and thus our access to documents is solely through the inverted index of a large scale search engine. Our main goal is to build the “best” short query that characterizes a document class using operators normally available within large engines. We show that surprisingly good classification accuracy can be achieved on average over multiple classes by queries with as few as 10 terms. Moreover, we show that optimizing the efficiency of query execution by careful selection of these terms can further reduce the query costs. More precisely, we show that on our set-up the best 10 terms query can achieve 90 % of the accuracy of the best SVM classifier (14000 terms), and if we are willing to tolerate a reduction to 86 % of the best SVM, we can build a 10 terms query that can be executed more than twice as fast as the best 10 terms query.
Finding %22Who Is Talking to Whom%22 in VoIP Networks via Progressive Stream Clustering.

Global distance%2Dbased segmentation of trajectories.
This work introduces distance-based criteria for segmentation of object trajectories. Segmentation leads to simplification of the original objects into smaller, less complex primitives that are better suited for storage and retrieval purposes. Previous work on trajectory segmentation attacked the problem locally, segmenting separately each trajectory of the database. Therefore, they did not directly optimize the inter-object separability, which is necessary for mining operations such as searching, clustering, and classification on large databases. In this paper we analyze the trajectory segmentation problem from a global perspective, utilizing data aware distance-based optimization techniques, which optimize pairwise distance estimates hence leading to more efficient object pruning. We first derive exact solutions of the distance-based formulation. Due to the intractable complexity of the exact solution, we present an approximate, greedy solution that exploits forward searching of locally optimal solutions. Since the greedy solution also imposes a prohibitive computational cost, we also put forward more lightweight variance-based segmentation techniques, which intelligently “relax ” the pairwise distance only in the areas that affect the least the mining operations.
A simulated annealing approach to the traveling tournament problem.
Automating the scheduling of sport leagues has received considerable attention in recent  years, as these applications involve significant revenues and generate challenging combinatorial  optimization problems. This paper considers the traveling tournament problem (TTP)  proposed in [10, 4] to abstract the salient features of major league baseball (MLB) in the  United States. It proposes a simulated annealing algorithm (TTSA) for the TTP that explores  both feasible and infeasible schedules, uses a large neighborhood with complex moves, and  includes advanced techniques such as strategic oscillation and reheats to balance the exploration  of the feasible and infeasible regions and to escape local minima at very low temperatures.
Sampling Search%2DEngine Results.
We consider the problem of e#ciently sampling Web search engine query results. In turn, using a small random sample instead of the full set of results leads to e#cient approximate algorithms for several applications, such as:  . Determining the set of categories in a given taxonomy spanned by the search results;  . Finding the range of metadata values associated to the result set in order to enable &#034;multi-faceted search;&#034;  . Estimating the size of the result set;  . Data mining associations to the query terms.
Sampling search%2Dengine results.
We consider the problem of e#ciently sampling Web search engine query results. In turn, using a small random sample instead of the full set of results leads to e#cient approximate algorithms for several applications, such as:  . Determining the set of categories in a given taxonomy spanned by the search results;  . Finding the range of metadata values associated to the result set in order to enable &#034;multi-faceted search;&#034;  . Estimating the size of the result set;  . Data mining associations to the query terms.
Steady state analysis of balanced%2Dallocation routing.
We compare the long-term, steady-state performance of a variant of the standard  Dynamic Alternative Routing (DAR) technique commonly used in telephone and ATM networks, to the performance of a path-selection algorithm based on the &#034;balanced-allocation&#034; principle [Y. Azer, A. Z. Broder, A. R. Karlin, and E. Upfal, SIAM J Comput 29(1) (2000), 180--200; M. Mitzenmacher, Ph.D. Thesis, University of California, Berkeley, August 1996]; we refer to this new algorithm as the Balanced Dynamic Alternative Routing (BDAR) algorithm. While DAR checks alternative routes sequentially until available bandwidth is found, the BDAR algorithm compares and chooses the best among a small number of alternatives. We show that, at the expense of a minor increase in routing overhead, the BDAR algorithm gives a substantial improvement in network performance, in terms both of network congestion and of bandwidth requirement. 2005 Wiley Periodicals, Inc. Random Struct. Alg., 26, 446--467, 2005 1. 
Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input.
We study the long-term (steady state) performance of a simple, randomized, local load balancing technique under a broad range of input conditions. We assume a system of n processors connected by an arbitrary network topology. Jobs are placed in the processors by a deterministic or randomized adversary. The adversary knows the current and past load distribution in the network and can use this information to place the new tasks in the processors. A node can execute one job per step, and can also participate in one load balancing operation in which it can move tasks to a direct neighbor in the network. In the protocol we analyze here, a node equalizes its load with a random neighbor in the graph.
A simple and deterministic competitive algorithm for online facility location.
This paper presents a deterministic and e#cient algorithm for online facility  location. The algorithm is based on a simple hierarchical partitioning and is  extremely simple to implement. It also applies to a variety of models, i.e.,  models where the facilities can be placed anywhere in the region, or only at  customer sites, or only at fixed locations. The paper shows that the algorithm  is O(log n)-competitive under these various models. It also shows that the  algorithm is O(1)-competitive with high probability and for any arrival order  when customers are uniformly distributed or when they follow a distribution  satisfying a smoothness property. Experimental results for a variety of scenarios  indicate that the algorithm behaves extremely well in practice.
Stability and Efficiency of a Random Local Load Balancing Protocol.
We study the long term (steady state) performance of a simple, randomized, local load balancing technique. We assume a system of n processors connected by an arbitrary network topology. Jobs are placed in the processors by a deterministic or randomized adversary. The adversary knows the current and past load distribution in the network and can use this information to place the new tasks in the processors. The adversary can put a number of new jobs in each processor, in each step, as long as the (expected) total number of new jobs arriving at a given step is bounded by #n. A node can execute one job per step, and also participate in one load balancing operation in which it can move tasks to a direct neighbor in the network. In the protocol we analyze here, a node equalizes its load with a random neighbor in the graph.
A Simulated Annealing Approach to the Travelling Tournament Problem.
Automating the scheduling of sport leagues has received considerable attention in recent  years, as these applications involve significant revenues and generate challenging combinatorial  optimization problems. This paper considers the traveling tournament problem (TTP)  proposed in [10, 4] to abstract the salient features of major league baseball (MLB) in the  United States. It proposes a simulated annealing algorithm (TTSA) for the TTP that explores  both feasible and infeasible schedules, uses a large neighborhood with complex moves, and  includes advanced techniques such as strategic oscillation and reheats to balance the exploration  of the feasible and infeasible regions and to escape local minima at very low temperatures.
Persistent Authenticated Dictionaries and Their Applications.
We introduce the notion of persistent authenticated dictionaries, that is, dictionaries where the user can make queries of the type &#034;was element e in set S at time t?&#034; and get authenticated answers. Applications include credential and certificate validation checking in the past (as in digital signatures for electronic contracts), digital receipts, and electronic tickets. We present two data structures that can efficiently support an infrastructure for persistent authenticated dictionaries, and we compare their performance.
